Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.
Implement the TwoSum class:
TwoSum()Initializes theTwoSumobject, with an empty array initially.void add(int number)Addsnumberto the data structure.boolean find(int value)Returnstrueif there exists any pair of numbers whose sum is equal tovalue, otherwise, it returnsfalse.
Example 1:
Input ["TwoSum", "add", "add", "add", "find", "find"] [[], [1], [3], [5], [4], [7]] Output [null, null, null, null, true, false] Explanation TwoSum twoSum = new TwoSum(); twoSum.add(1); // [] --> [1] twoSum.add(3); // [1] --> [1,3] twoSum.add(5); // [1,3] --> [1,3,5] twoSum.find(4); // 1 + 3 = 4, return true twoSum.find(7); // No two integers sum up to 7, return false
Constraints:
-105 <= number <= 105-231 <= value <= 231 - 1- At most
5 * 104calls will be made toaddandfind.
Average Rating: 4.72 (18 votes)
Solution
Approach 1: Sorted List
Intuition
First of all, the problem description is not terribly clear on the requirements of time and space complexity. But let us consider this as part of the challenge or a freedom of design. We could figure out the desired complexity for each function, by trial and error.
This is one of the followup problems to the first programming problem on LeetCode called Two Sum, where one is asked to return the indice of two numbers from a list that could sum up to a given value.
Let us take the inspiration from the origin problem, by keeping all the incoming numbers in a list.
Given a list, one of the solutions to the Two Sum problem is called Two-Pointers Iteration where we iterate through the list from two directions with two pointers approaching each other.
However, one of the preconditions for the Two-Pointers Iteration solution is that the input list should be sorted.
So now, here are the questions:
-
Should we keep the list in order while inserting new numbers in the function
add(number)? -
Or should we do the sorting on demand, i.e. at the invocation of
find(value)?
We will address the above two questions later in the Algorithm section.
Algorithm
Let us first give the algorithm of Two-Pointers Iteration to find the two-sum solution from a sorted list:
-
We initialize two pointers
lowandhighwhich point to the head and the tail elements of the list respectively. -
With the two pointers, we start a loop to iterate the list. The loop would terminate either we find the two-sum solution or the two pointers meet each other.
-
Within the loop, at each step, we would move either of the pointers, according to different conditions:
-
If the sum of the elements pointed by the current pointers is less than the desired value, then we should try to increase the sum to meet the desired value, i.e. we should move the
lowpointer forwards to have a larger value. -
Similarly if the sum of the elements pointed by the current pointers is greater than the desired value, we then should try to reduce the sum by moving the
highpointer towards thelowpointer. -
If the sum happen to the desired value, then we could simply do an early return of the function.
-
-
If the loop is terminated at the case where the two pointers meet each other, then we can be sure that there is no solution to the desired value.
The usage pattern of the desired data structure in the online judge, as we would discover, is that the
add(number)function would be called frequently which might be followed a less frequent call offind(value)function.
The usage pattern implies that we should try to minimize the cost of add(number) function. As a result, we sort the list within the find(value) function instead of the add(number) function.
So to the above questions about where to place the sort operation, actually both options are valid and correct. Due to the usage pattern of the two functions though, it is less optimal to sort the list at each add operation.
On the other hand, we do not do sorting at each occasion of find(value) neither. But rather, we sort on demand, i.e. only when the list is updated. As a result, we amortize the cost of the sorting over the time. And this is the optimization trick for the solution to pass the online judge.
Complexity Analysis
-
Time Complexity:
-
For the
add(number)function: O(1), since we simply append the element into the list. -
For the
find(value)function: O(N⋅log(N)). In the worst case, we would need to sort the list first, which is of O(N⋅log(N)) time complexity normally. And later, again in the worst case we need to iterate through the entire list, which is of O(N) time complexity. As a result, the overall time complexity of the function lies on O(N⋅log(N)) of the sorting operation, which dominates over the later iteration part.
-
-
Space Complexity: the overall space complexity of the data structure is O(N) where N is the total number of numbers that have been added.
Approach 2: HashTable
Intuition
As an alternative solution to the original Two Sum problem, one could employ the HashTable to index each number.
Given a desired sum value
S, for each numbera, we just need to verify if there exists a complement number (S-a) in the table.
As we know, the data structure of hashtable could offer us a quick lookup as well as insertion operations, which fits well with the above requirements.
Algorithm
-
First, we initialize a hashtable container in our data structure.
-
For the
add(number)function, we build a frequency hashtable with the number as key and the frequency of the number as the value in the table. -
For the
find(value)function, we then iterate through the hashtable over the keys. For each key (number), we check if there exists a complement (value - number) in the table. If so, we could terminate the loop and return the result. -
In a particular case, where the number and its complement are equal, we then need to check if there exists at least two copies of the number in the table.
We illustrate the algorithm in the following figure:
Complexity Analysis
-
Time Complexity:
-
For the
add(number)function: O(1), since it takes a constant time to update an entry in hashtable. -
For the
find(value)function: O(N), where N is the total number of unique numbers. In the worst case, we would iterate through the entire table.
-
-
Space Complexity: O(N), where N is the total number of unique numbers that we will see during the usage of the data structure.
Isn't the time complexity for Approach 2's find function linear? Looking up the compliment is done in constant time, but in the event that no valid pair exists, the algorithm will loop through the entire hash table looking for compliments.
The HashMap solutions is hard to read, modified a bit:
class TwoSum {
private HashMap<Integer, Integer> num_counts;
/** Initialize your data structure here. */
public TwoSum() {
this.num_counts = new HashMap<>();
}
/** Add the number to an internal data structure.. */
public void add(int number) {
this.num_counts.put(number, num_counts.getOrDefault(number, 0) + 1);
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
for(Integer key : this.num_counts.keySet()) {
int complement = value - key;
if(complement != key) {
if(this.num_counts.containsKey(complement))
return true;
} else if(this.num_counts.get(key) > 1)
return true;
}
return false;
}
}
Is the constraint of this problem correct? If add takes O(1) and time takes O(N). Then if I add 2*10^4 different numbers and find 3*10^4 times then TLE will occur.
Discussion topic: https://leetcode.com/problems/two-sum-iii-data-structure-design/discuss/884946/The-constraint-is-WRONG
Last Edit: January 11, 2020 11:43 PM
I think we can get linear add() and constant time find(), if we keep a Set of all the sums.
When we add, compute the pair-wise sum of the new element with all the existing elements, and add those pair-wise sums to the set.
Just something to consider, depending on the behavior in traffic on those 2 API endpoints of this class ;)
Edit: I'm getting TLE with this implementation. It looks like there are more calls to add() than find() in the test cases.
September 26, 2020 3:50 PM
In the first solution the author forgot to do self.is_sorted = True at line 37.
February 15, 2020 1:12 AM
You can do sorted array in O(n) time, if you will maintain it with each addition.
Then add(number) -> O(n)
and find(value) -> O(n)
Space for the sorted array O(number of unique items)
This Leetcode question is useless. Basically, we solve the problem using Two Sum or Two Sum II. The streaming thing does not add value at all.
Will the Two-Pointer solution work when negative numbers are part of the list (allowed as per problem statement)?
Lets say we maintain the list as sorted, and we are asked to find(-8) when the list currently looks like this:
[-5,-4,-3,-2,-1]
Clearly, there is a solution (-8 == -5 + -3).
But the algorithm, as detailed above, would work as per the table below and declare no success.
Iter | Low | High | Sum | TwoSum |
-----+-----+------+-----+--------|
0 | 0 | 4 | -6 | -8 |
1 | 1 | 4 | -5 | -8 |
2 | 2 | 4 | -4 | -8 |
3 | 3 | 4 | -3 | -8 |
4 | 4 | 4 | FAIL| -8 |
Isn't the time complexity for Approach:2's 'find' O(n^2) since looking up each complement will also involve iterating through the whole data structure? Can someone explain please? Thanks in advance!
class TwoSum(object):
def __init__(self):
self.nums = []
def add(self, number):
"""
Add the number to an internal data structure..
:type number: int
:rtype: None
"""
number = self.nums.append(number)
def find(self, value):
"""
Find if there exists any pair of numbers which sum is equal to the value.
:type value: int
:rtype: bool
"""
numbers = self.nums
seen = set()
for i, num in enumerate(numbers):
rem = value - num
if rem not in seen:
seen.add(num)
else:
return True
return False
Your TwoSum object will be instantiated and called as such:
obj = TwoSum()
obj.add(number)
param_2 = obj.find(value)
Time Submitted | Status | Runtime | Memory | Language |
|---|---|---|---|---|
| 06/19/2021 08:39 | Accepted | 152 ms | 24.7 MB | cpp |
| 06/19/2021 08:39 | Runtime Error | N/A | N/A | cpp |
xxxxxxxxxxclass TwoSum {public: /** Initialize your data structure here. */ unordered_map<long,int>mp; vector<long>v; int idx = 0; TwoSum() { } /** Add the number to an internal data structure.. */ void add(int number) { mp[number] = idx; v.push_back(number); idx++; } /** Find if there exists any pair of numbers which sum is equal to the value. */ bool find(int value) { for(int i=0;i<v.size();i++) { if(mp.find(value - v[i]) != mp.end() && i != mp[value-v[i]]) return true; } return false; }};/** * Your TwoSum object will be instantiated and called as such: * TwoSum* obj = new TwoSum(); * obj->add(number); * bool param_2 = obj->find(value); */

